package basic.study.wantOffer.chapter5;

/**
 * @ClassName Problem42
 * @Description 连续子数组的最大和
 * @Company inspur
 * @Author Kevin
 * @Date 2020/5/25 10:35
 * @Version 1.0
 */
public class Problem42 {
    class GreatestSumOfSubarrays {
        boolean InvalidInput = false;
        public int FindGreatestSumOfSubArray(int[] array) {
            if (array == null || array.length <= 0) {
                InvalidInput = true;
                return 0;
            }
            InvalidInput = false;
            int sum = array[0];
            int maxSum = array[0];
            for (int i = 1; i < array.length; i++) {
                if (array[i] < 0) {
                    sum = array[i];
                } else {
                    sum += array[i];
                }

                if (sum > maxSum) {
                    maxSum = sum;
                }
            }
            return maxSum;
        }


        public int dp(int[] arr) {
            if (arr == null || arr.length <= 0) {
                return 0;
            }
            int[] dp = new int[arr.length];
            dp[0] = arr[0];
            for (int i = 1; i < arr.length; i++) {
                dp[i] = Math.max(arr[i], dp[i-1] + arr[i]);
            }
            return dp[arr.length-1];
        }
    }


}
